package Comprehensive_02;

import java.util.Arrays;

/**
 * 荷兰国旗问题：
 *      问题一：
 *          给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，
 *          大于num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)
 *      问题二(升级版):
 *          给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，
 *          等于num的数放在数组的中间.
 *          大于num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)
 */
public class Test9 {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 6, 7, 8, 3, 4, 2, 3, 4, 5, 1, 3};
        netherlandsFlag(arr,4);
        System.out.println(Arrays.toString(arr));
    }

    public static void netherlandsFlag(int[] arr, int num){
        int min = -1;
        int max = arr.length;
        int index = 0;
        while (index < max){
            if (arr[index] < num) {
                swap(arr,index, ++min);
            } else if (arr[index] > num) {
                swap(arr,index, --max);
                continue;
            }
            index++;
        }
    }

    public static void swap(int[] arr, int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

}
